package com.justnow.offer;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author justnow
 * Created on 2020-09-04
 * Description
 * leetcode-46
 */
public class Solution19 {

    public List<List<Integer>> premute(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0)
            return res;
        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, List<Integer> path
                    ,boolean[] used
                    ,List<List<Integer>> res) {


        // 变量path所指向的列表 在深度优先遍历的过程中只有一份，深度优先遍历完成以后，回到了根节点，成为空列表。
        // 在java中，参数传递是值传递，对象类型变量在传参的过程中，复制的是变量的地址，
        // 这些地址被添加到res变量，但实际上指向的是同一块内存地址。所以需要用new ArrayList<>(path)进行一次copy，
        // 从而记录当期path的状态
        // 此时，已经递归到了叶子节点，需要返回
        if (depth == len) {
            //res.add(path); 返回的是空列表
            res.add(new ArrayList<>(path));
            return;
        }

        // 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                dfs(nums, len, depth + 1, path, used, res);
                // 重置状态
                // 下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }


    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute2(int[] nums) {
        dfs(0, nums);
        return res;
    }

    public void dfs(int x, int[] nums) {
        if (x == nums.length - 1) {
            ArrayList<Integer> temp = new ArrayList<>();
            for (int num : nums) {
                temp.add(num);
            }
            res.add(temp);
        }

        for(int i = x; i < nums.length; i++) {
            swap(i, x, nums);
            dfs(x + 1, nums);
            swap(x, i, nums);
        }
    }

    public void swap(int a, int b, int[] nums) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution19 solution19 = new Solution19();
        List<List<Integer>> lists = solution19.permute2(nums);
        System.out.println(lists);
    }

}
